\section{Trees} 
\label{sec:Tree} 

A useful tool in bounding the cover time for simple random walks is Matthew's Theorem ~\cite{matthews1988covering,lovasz-survey}, which bounds the expected cover time of a graph by the maximum expected hitting time $h_{u,v}$ between any two vertices $u$ and $v$ multiplied by a $O(\log n)$ factor. Here we show that this result can be extended to cobra walks. \onlyShort{The full proof can be found in the full version of the paper, but the key idea is that we map the cobra walk on $G$ to a simple walk on much larger graph derived from $G$ and then show that this satisfies the conditions for the proof of Matthew's Theorem on simple walks.} 

\begin{theorem}{\textbf{(Matthew's Theorem for Cobra Walks)}}
\label{tree:Matthews}
Let $G$ be a connected graph on n vertices. Let $W$ be a cobra walk on G
starting at an arbitrary vertex. Then the cover-time of $W$ on $G$,
$C(G)$, is bounded from above by 
$O(h_{max} \log n)$ in expectation and with high probability.
\end{theorem}
\onlyLong{
\begin{proof}  
We follow the proof outlined in \cite{lovasz-survey}. We first show the following claim.

Claim: Let $b$ be the expected number of steps before a cobra walk visits more than half of the vertices. Then $b \leq 2h_{max}$.

%Let us assume that the number of vertices is odd, i.e., $n = 2k+1$ (the proof for the even case is similar).
Proof of Claim: Let $\rho_v$ be the time when vertex $v$ is first visited by the cobra walk. Arrange the $\rho_v$'s
in increasing order.  Let $\ell =\lceil (n+1)/2 \rceil$.
Then the time $\beta$ when the cobra walk reaches (for the first time)
more than half of the vertices is the $\ell$-th element in the above order of the $\rho_v$s.
Hence,
$$\sum_{v \in V} \rho_v \geq (n-\ell+1) \beta.$$
Taking expectation on both sides we have,
$$b = E[\beta] \leq \frac{1}{n-\ell+1} \sum_{v \in V} E[\rho_v] \leq \frac{n h_{max}}{n-\ell+1} \leq 2 h_{max},$$
since $\sum_{v \in V} E[\rho_v] \leq n h_{max}$ and $\frac{n}{n-\ell+1} \leq 2$.
Hence the claim.

The above claim says that in $2h_{max}$ steps the cobra walk will visit more than $n/2$ vertices;  by a similar argument,
in another $2h_{max}$ steps, the cobra walk will visit half of the rest of the vertices. Repeating the argument $\log_2 n$ times,
it follows that all vertices will be visited in expected $O(h_{max} \log n)$ steps.

We next show that the above bound on the cover time also holds with high probability.
Let's partition the visit of the cobra walk into $\log_2 n$ different stages according to the number of vertices it visits:  the first $n/2$ (different) vertices (first stage),
then the next $n/4$ vertices (second stage), and so on. By the above claim, each stage finishes in at most $2 h_{max}$ steps in expectation.
By Markov's inequality, this implies that, with probability at least $1/2$, each stage finishes in at most $4 h_{max}$ steps.
If the cobra walk finishes a stage in at most $4 h_{max} $ steps, then we call it a ``success"; the probability of this happening is at least $1/2$.
For the sake of analysis, assume that if the cobra walk fails to complete a particular stage in at most $4 h_{max}$ steps, then it repeats this stage again (this can only increase the cover time). Call each such repetition a trial.  Accordingly, the cobra walk needs $\log_2 n$ successes to finish all stages.
In a total of $12 \log_2 n$ trials, the expected number of successes is at least $6 \log_2 n$. Applying a Chernoff bound \cite{upfal}, 
the probability that the number of successes in $12 \log _2 n $ trials is less than $\log_2 n$ is less than $1/n^2$.
Thus, with high probability, the number of repetitions is bounded by $O(\log n)$ overall. Since each repetition takes $4 h_{max}$ steps,
the cover time is $O(h_{max} \log n)$ with high probability.

\iffalse
We adopt the language of ~\cite{matthews1988covering}. Rather than viewing a cobra walk as multiple pebbles moving over a graph, we will view it as a Markov process $M'$ of its own. In this process, the state space consists of $2^n$ states, each of which corresponds to a particular subset of the vertices that contain pebbles. Transitions between states occur with a probability equal to the probability of one particular pebble configuration in the original graph giving rise to the next state. 

We fix an initial position $a_0$ of $M'$ and a collection of $n$ Borel subsets of $M', \{A_1,\ldots, A_n\}$ to be visited. Here $A_i$ represents the set of all states of $M'$ in which vertex $i$ in $G$ contains a pebble. For any non-empty collection $\{A_1,\ldots,A_i\}$ of Borel subsets of $M'$ we then define $T(A_j) = \inf \{ t \geq 0 : X(t) \in A_j\}$ for $j = 1,\ldots, i$. That is, $T(A_j)$ is the smallest time t such that the walk $X$ on $M'$ visits a member of $A_j$. We also define $T(A_1,\ldots,A_i) = \max_{j = 1,\ldots,i} T(A_j)$. We now define:
\begin{equation*}
\mu_+ = \max_{i = 1, \ldots, N} \sup_{a \notin A_i} E_a T(A_i). 
\end{equation*} 
$\mu_+$ is $h_{max}$ in the standard language of random walks. Then from Theorem 2.6 of ~\cite{matthews1988covering}, 
\begin{equation*}
ET(A_1,\ldots,A_n) \leq \mu_+  \sum_{i=1}^{n} \frac{1}{i} 
\end{equation*}
thus proving the lemma. 
\fi
\end{proof}
}

Matthew's theorem for cobra walks is used in proving the cover time for trees and grids. 

\begin{theorem}
\label{tree:main_result} 
For any tree, the cover time of a cobra walk (with branching factor $k \geq 2$) starting from any vertex is  $O(n \log n)$ w.h.p.
\end{theorem}

\junk{
It is also easy to see the following corollary for the line:
\begin{corollary}
Let L be a line graph of length $n$. The the expected cover time of $L$ is $O(n)$. 
\end{corollary} 
}

We will prove our main result by calculating the maximum hitting time
of a cobra walk on a tree $T$ and then applying Matthew's
theorem. Cobra walks on trees are especially tractable because they
follow two nice properties. Since a tree has a unique path between any
two vertices, when analyzing progression of the cobra walk from a source vertex
to a target vertex, we only need keep track of the pebble closest to the
target (which may change in each time step). In addition, the fact that there is one simple path between
any two vertices limits the number of collisions we need to keep track
of, a property which is not true for general graphs and makes cobra
walks harder to analyze on them. For this section, we fix the branching
factor $k=2$. For $k>2$ but still constant, the cover time would not
be asymptotically better. This is because, as we will see, our analysis involves
showing stochastic dominance of a biased random walk with transition properties
similar to that of tokens moving from an active vertex in a cobra walk. As such, having 
a branching factor larger than $2$ boosts the bias probabilities, but only by a
constant. This therefore does not affect the asymptotic hitting time result, and hence not
the cover time.  

The general idea behind the proof is as follows. We consider the longest
path in the tree. Along each vertex in this path,
except for the first and last, there will be a subtree rooted at that
vertex. If a cobra walk's closest pebble to the endpoint is at vertex
$l$, the walk from this point can either advance with at least one
pebble, or it can not advance by either backtracking along the path,
going down the subtree rooted at $l$, or both. We show via a
stochastic dominance argument that a biased random walk from $l$,
whose transition probabilities are tuned to be identical to
cobra walk's, will next advance to $l+1$ in a time that is dominated
primarily by the size of the subtree at $l$. This is done by analyzing
the return times in the non-advancement scenarios listed above. Thus
summing up over the entire walk, the hitting time is dominated by a
linear function of the size of the entire tree.

%gopal --- In the above para: why "longest" path? There is only one path between any two vertices.
%gopal --- perhaps a simple figure illustrating the above will be great.
%scott --- this is the longest path betwen any two nodes, so basically the ``spine'' of the tree
%gopal --- I am still confused, there is only one path between any two nodes in the tree...

In Lemma \ref{tree:return} we bound the return time of a cobra walk to
the root of a tree. 


\begin{lemma}
\label{tree:return} 
Let $T$ be a tree of size $n$. Pick a root, $r$, and let $r$ have $d$
children. Then a cobra walk on $T$ starting at $r$ will have a return
time to $r$ of $4n/ d$.
\end{lemma}
\begin{proof}
To show that the Lemma holds for a cobra walk, we will actually show
that it holds for a biased simple random walk with transition
probabilities modified to resemble those of a cobra walk. We then use
a stochastic dominance argument to show that the return time of the
cobra walk dominates the return time of the biased simple random walk.

For this simple random walk, we start at $r$, and assume that $r$ has $d$ children. In the first step the walk picks one of the children of $r$, $r_i$.  Let $(d_i +1)$ be the degree of $r_i$ (meaning that $r_i$ has one parent, $r$, and $d_i$ children). Then we define transition probabilities as follows: $p$ is the probability of returning to $r$ in the next step, and $q$ is the probability of continuing down the tree to a child of $r_i$. They are given as:
$p = \left(1 - \left( \dfrac{d_i}{(d_i +1)} \right)^2 \right)$,
$ q =  \left( \dfrac{d_i}{(d_i +1)} \right)^2 $,
$\frac{q}{p} = \frac{(d_i)^2}{(2d_i + 1)}$.
Note that these are the exact same probabilities that a cobra walk at vertex $r_i$ would have for sending (not sending) at least one (any) pebbles back to the root.

The rest of the proof follows by mathematical induction. Consider a tree $T$ that has only two levels. Starting from $r$, the return time, 2, is constant, thus the relationship holds. For the inductive case, assume that the hypothesis holds. Denote $ret(T)$ the return time to the root of $t$, and $N(v)$ to be the children of $v$ in the rooted tree $T$. For a root $r$ with children $r_i$, denote $T_i$ to be the induced subtree rooted at $r_i$. Then:
\begin{eqnarray*}
\E[ret(T)] &=& 1 + \frac{1}{d} \sum_{r_i \in N(r)} 1+ \E[\text{number of visits to $r_i$ until walk returns to $r$}]\cdot  \E[ret(T_i)] \\ 
&\leq& 2 + \frac{1}{d} \sum_{r_i \in N(r)} \frac{q}{p} \cdot \frac{c |T_i|}{d_i} \\
&=& 2 + \frac{c}{d} \sum \frac{d_i^2}{2 d_i + 1} \cdot \frac{|T_i|}{d_i} \\
&=& 2 + \frac{c}{d} \sum \frac{d_i}{2 d_i + 1} |T_i| \\
&\leq& 2 + \frac{c}{2d} (n - 1) < \frac{4n}{d}
\end{eqnarray*}
for $c = 4$, where $ret(T_i) \leq 4 |T_i|/d_i$ by the induction hypothesis. Note that the $q/p$ that appears in the second line of the equations above represents the mean of a negative binomial random variable describing the number of heads needed in a series of coin tosses until the first tails is observed.  Here heads indicates \textbf{not} moving one hop up the tree towards the root, and tails is equivalent to doing so. 

Next we show the stochastic dominance of the return time of the biased
random walk to the root over the return time of a cobra walk to the
root. Let $X$ be the random variable representing the number of time
steps until a biased (single) random walk starting at $r$ returns to
$r$. Let $Y$ be the random variable associated with the return time of
a cobra walk starting at $r$ to $r$. Note that $X$ and $Y$ are defined
on the same probability space $\Omega$, namely the integers $\geq 2$.

\junk{
We now create a coupling between X and Y. Denote the random vector
$(\tilde{X},\tilde{Y})$ with join distribution $\tilde{P}(\dot,\dot)$
over probability space $\Omega \times \Omega$ such that the marginal
distribution of $\tilde{X}$ coincides with the distribution of $X$ and
the marginal distribution of $\tilde{Y}$ coincides with the
distribution of $Y$. We let $(\tilde{X},\tilde{Y})$ represent the
respective return times of a biased random walk and a cobra walk to
$r$, when started from $r$ at time $0$. We next argue that
$\tilde{P}(\tilde{X} \leq \tilde{Y}) = 1$ and thus that $X$ dominates
$Y$ (i.e. $Y$ is stochastically smaller than $X$.
}

For $X,Y = 2$ note that $\prob{X =2} \leq \prob{Y=2}$\junk{ and hence
  $\tilde{P}(\tilde{X} = 2 \leq \tilde{Y} = 2)$}, since the random
walk will occupy only one child of $r$, while the cobra walk will
occupy one or two children. If it occupies two children, the
probability that at least one token returns to $r$ is greater than in
the single vertex case. Similarly, for higher values of $X,Y$, the
vertex occupied by the random walk token will always be a subset of
the vertices occupied by the tokens closest to $r$ in the cobra
walk. As such, the probability of the cobra walk moving one step
closer to return will be at least the probability of the random walk's
token doing so, and applying this recursively we have $\prob{X \geq x}
\geq \prob{Y \geq x}$\junk{, implying $\tilde{P}(\tilde{X} \leq
  \tilde{Y}) = 1$ for all values of $x$}. (Note that $x$ can only take
on even values, as $T$ is a bipartite graph).

\end{proof} 

Next we show an upper bound on the expected amount of time it will take until a cobra walk moves one vertex closer towards the target vertex along the path from the source to the target. 

\begin{lemma}
\label{tree:singlestep}
Fix a path in a tree $T$ made up of vertices   $1,\ldots,l,(l+1),\ldots,
t$.  Then, the expected time it takes for a cobra walk starting at
vertex $l$ to get to $l+1$ with at least one token can be bounded as:
\begin{equation}
h_{l,(l+1)}  \leq \frac{3}{2} + \frac{12}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|  
\end{equation}
where $T_l$ is the induced subtree formed by vertex $l$ and its
neighbors not in $\{l-1,l+1\}$, and all of their respective descendants.
\end{lemma}
%\onlyShort{The proof can be found in the long version of the paper.}
Informally, we prove that the one-step hitting time is bounded from above by the expected hitting time of the worst case scenario that either both pebbles go back along the path or both  go down the subtree rooted at $l$. We then establish a simple recurrence relation.

\begin{figure}
\begin{center}
	\includegraphics[scale=0.8]{TreeFigure.pdf} 
	\caption{Local topology of tree for lemma~\ref{tree:singlestep}} 
\end{center}
\end{figure}

 
%\onlyLong{
\begin{proof}
Vertex $l$ has one edge to the vertex $l-1$, one edge to vertex $l+1$, and $d_l$ additional neighbors. $T_l$ is the induced subtree of $T$ formed by $l$, the $d_l$ neighbors of $l$ that are not in $\{l-1,l+1\}$, and all other vertices connected to the $d_l$ neighbors of $l$. 

\begin{itemize}
\item  Probability of a pebble going from $l$ to $l+1 = p = \left(1 - \left(\dfrac{(d_l+1)}{(d_l+2)}\right)^2 \right)$
\item Probability of a pebble not going from $l$ to $l+1 = 1 - p = q$. 
\item Probability of a cobra walk sending both pebbles from $l$ to $l-1$ conditioned on it $not$ sending any pebbles from $l$ to $l+1 = q^{'}_l = \left(\dfrac{1}{(d_l+1)^2}\right)$ 
\item Probability of a cobra walk sending at least one pebble to the subtree $T_l$ conditioned on its not sending any pebbles to $l+1 = q^{''}_l = \left(\dfrac{(d_l)}{(d_l + 1)} \right)^2 + 2\left(\dfrac{d_l}{(d_l+1)^2}\right) = \dfrac{d_l^2 + 2d_l}{(d_l + 1)^2}$ 
\end{itemize}
Note that, conditioned on a pebble not advancing to vertex $l+1$, there are  three disjoint events:
\begin{itemize}
	\item  (A) Both pebbles go to $l-1$, 
	\item (B) one pebble goes to $l-1$ and one pebble goes into subtree $T_l$, and 
	\item (C) both pebbles go into $T_l$. 
\end{itemize} 
	We define an alternate event $B'$ as the event that there is only one pebble at $l$, and it goes to a child in $T_l$. Therefore, it is not technically in the space of cobra walk actions. However, this modified cobra walk stochastically dominates the original cobra walk, since it corresponds to a subset of the possible cobra walks actions from $l$: the case where both pebbles move to the same vertex in $T_l$. If we let $R$ be the  time until first return of the cobra walk to $l$ conditioned on no pebble going to $l+1$ from $l$ initially, we wish to show that $E[R|B] \leq E[R|B']$ and that $E[R|C] \leq E[R|B']$. What is the relationship between $B$ and $B'$? Consider two random variables, $X$ and $Y$, and let $X$ be the time until first return of a pebble that travels from $l$ to $l-1$, $Y$ be the time until first return of a pebble that travels into $T_l$. Then $R|B$ is just another random variable, $U = \min(X,Y)$. Since $U \leq Y$ over the entire space, $E[U] \leq E[Y]$, and clearly $R|B'$ is equivalent to $Y$. Thus $E[R|B] \leq E[R|B']$. It is also easy to see that $E[R|B'] \geq E[R|C]$. Thus by the law of total expectation we have: 
\begin{eqnarray*}
E[R] &=& E[R|A]\Pr(A) + E[R|B]\Pr(B) + E[R|C]\Pr(C) \\
&\leq& E[R|A] \Pr(A)+ (\Pr(B) + \Pr(C))E[R|B'] \\
&=& E[R|A] \Pr(A) + (1 - \Pr(A))E[R|B'] 
\end{eqnarray*}

 Then the hitting time can be expressed as:  
\begin{eqnarray*}
h_{l,l+1} &\leq& p + q(E[R] + h_{l,l+1}) \\
\Rightarrow (1 - q) h_{l,l+1} &\leq& p + q(E[R]) \\
\Rightarrow h_{l,l+1} &\leq& 1 + \frac{q}{p} (q^{'}_l (1 + h_{l-1,l}) + q^{''}_l r(T_l)) 
\end{eqnarray*}
Note that $q/p = \frac{(d_l + 1)^2}{(2d_l + 3)}$. Since $r(T_l) \leq 4 |T_l| / d_l$ by Lemma \ref{tree:return}, we continue with:
\begin{eqnarray*}
h_{l,l+1} & \leq & 1 + \frac{(d_l +1)^2}{(2d_l + 3)} \frac{1}{(d_l + 1)^2}(1 + h_{l-1,l}) +  \frac{(d_l +1)^2}{(2d_l + 3)} \frac{(d_l^2 + 2d_l)}{(d_l + 1)^2} \frac{4 |T_l|}{d_l} \\
& \leq & 1 + \frac{1}{5} (1 + h_{l-1,l}) + \frac{12}{5} |T_l|\\
& = & \frac{6}{5} + \frac{12}{5} |T_l| + \frac{h_{l-1,l}}{5},  
\end{eqnarray*}
for $d_l \geq 1$. 

%gopal --- Why the above statement is true w.h.p? We are talking about expectations here, right? 
%scott --- Changed
%gopal-- I removed "in expectation", since by default hitting time  is defined in expectation, right?

We next apply this formula to $h_{l-1,l}$ and continue the recurrence to get the bound in its expanded form: 
\begin{eqnarray*}
h_{l,l+1} & \leq & \frac{6}{5} \sum_{i = 0}^{l} \left(\frac{1}{5}\right)^i + \frac{12}{5} \left( |T_l| +  \left(\frac{1}{5}\right) |T_{l-1}| + \left(\frac{1}{5}\right)^2 |T_{l-2}| + \dots + \left(\frac{1}{5}\right)^{l-2} |T_{2}|\right),
\end{eqnarray*}
where we use the fact that $h_{0,1} \le 1$.  We simplify the above to obtain the desired result.
$$h_{l,l+1} \leq \frac{3}{2} + \frac{12}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|.$$
\end{proof}
Note that we stop at $T_2$, since for vertex $1$ on the path, having a tree rooted at it would violate the assumption that $1,\ldots,l$ is the path with maximal hitting time. 
%}

We are finally ready to prove our main result for the tree,
Theorem~\ref{tree:main_result}, that the cobra walk cover time of an
arbitrary tree occurs in $O(n \ln n)$ steps.

\begin{proof}
By Matthew's Theorem for cobra walks, $C(G) \leq O(\log n)
h_{max}$. We just need to prove that $h_{max}$ is at most linear in
the size of the tree.

Let $P$ be the path for which $h_{u,v}$ is maximized, and let the path
consist of the sequence of vertices $1,2,\ldots,t$. As in the proof of
the single-step hitting time, we note that for all but the first and
last vertices on $P$, there is a subtree $T_l$ of size $|T_l|$ rooted
at each vertices. Because $h_{1,t} \leq h_{1,2} + h_{2,3} + \ldots
h_{t-1,t}$ we obtain the desired result from Lemma
\ref{tree:singlestep} as follows:
\begin{eqnarray*}\\
h_{1,t} &\leq& \frac{3}{2} t + \frac{12}{5} \sum_{j = 2}^{t-1}  \left[ |T_j| \sum_{i = 0}^{\infty} \left(\frac{1}{5}\right)^i \right] \\
&\leq& \frac{3}{2} t + \frac{12}{5} \frac{5}{4}  \sum_{j=2}^{t-1} |T_j| \le \frac{9n}{2}.
\end{eqnarray*} 
\end{proof}
